#pragma once

#include<utility>
#include<iostream>
#include<assert.h>
#include<vector>
#include<time.h>
#include<string>

using namespace std;

enum Colour
{
	RED,
	BLACK
};

//红黑树节点，里面存的值为T。
//如果是set,T即为Key
//如果是map,T为pair<Key, T>
//即：节点中要么存一个值，要么存一个键值对
template<class T>
struct RBTreeNode
{
	//RBTreeNode(T data)
	RBTreeNode(const T& data)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _data(data)
	{}

	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Colour _col;
	T _data;
};

//红黑树迭代器，内部封装了红黑树节点的指针。
//操作符重载: ++/--/==/!=/*/->/
template<class T, class Ref, class Ptr>
class RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
public:
	RBTreeIterator(Node* root)
		: _pNode(root)
	{}

	Ref operator*()
	{
		return _pNode->_data;
	}

	Ptr operator->()
	{
		return &(_pNode->_data);
	}

	//前置++，++it
	//访问中序的后一个
	Self& operator++()
	{
		//左->中->右
		Node* cur = _pNode;
		Node* parent = nullptr;
		if (cur == nullptr)
		{
			cout << "无法对空节点++()操作" << endl;
			assert(false);
		}

		//如果右不为空，访问右子树最左节点
		if (cur->_right)
		{
			cur = cur->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			//return Self(cur); ---> 这样只是会返回一个++后的值，并不会改变it ---> ++it是要改变it，然后把it返回
			_pNode = cur;
			return *this;
		}
		//如果右为空， 该子树已经访问完了
		else
		{
			//parent为空，访问完了，返回end
			parent = cur->_parent;
			if (parent == nullptr)
			{
				//return Self(nullptr);
				_pNode = nullptr;
				return *this;
			}
			//我是父亲左，访问父亲
			else if (cur == parent->_left)
			{
				//return Self(parent);
				_pNode = parent;
				return *this;
			}
			//我是父亲右，父亲这颗树也已经访问完了，向上寻找直到cur为父亲左，访问父亲，或者向上寻找直到父亲为空。
			else
			{
				while (parent)
				{
					//我是父亲左，访问父亲
					if (cur == parent->_left)
					{
						//return Self(parent);
						_pNode = parent;
						return *this;
					}
					//沿路径向上寻找
					cur = parent;
					parent = parent->_parent;
				}
				//return Self(nullptr);
				_pNode = nullptr;
				return *this;
			}
		}
	}

	//左<---中<---右
	Self& operator--()
	{
		//左不为空，访问其左子树最右节点
		//左为空，该子树已经访问完了，沿路径向上寻找
		//                            父亲为空 ---> 该树已经访问完了，让迭代器指向end()
		//                            我是父亲的右 ---> 访问父亲
		//                            我是父亲的左 ---> 父亲这颗子树也已经访问完了，继续向上寻找
		Node* cur = _pNode;
		Node* parent = nullptr;
		
		assert(_pNode);

		if (_pNode->_left)
		{
			cur = cur->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_pNode = cur; //改变该迭代器本身

			return *this; //返回该迭代器
		}
		else
		{
			parent = cur->_parent;

			//如果cur是parent的左会进入循环，并沿路径向上找，直到cur为parent的右或者parent为空，然后跳出循环
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_pNode = parent;
			return *this;
		}


	}

	bool operator!=(Self right)
	{
		Self left = *this;
		return left._pNode != right._pNode;
	}

	bool operator==(Self right)
	{
		Self left = *this;
		return left._pNode == right._pNode;
	}

public:
	Node* _pNode;
};

//传K是因为要拿K比较时用，T是节点中存的值的类型，可能是K（set），也可能是pair<K, V>（map）
template<class K, class T, class KeyOfT> //仿函数，用来从T里面取出Key的值
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_Iterator;



	RBTree()
		: _root(nullptr)
	{}

	//拷贝构造
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		//copy(t._root);
		//_root = copy(t._root);
	}

	Node* copy(const Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		
		//处理
		Node* newNode = new Node(root->_data); //data
		newNode->_col = root->_col; //col

		Node* left = copy(root->_left);
		Node* right = copy(root->_right);
		newNode->_left = left; //左
		newNode->_right = right; //右
		
		//left->_parent = right->_parent = newNode; //parent
		//parent
		if (left)
			left->_parent = newNode;

		if (right)
			right->_parent = newNode;

		return newNode;
	}

	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}

	Iterator Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;

		while (cur)
		{
			if (key > kot(cur->_data))
			{
				cur = cur->_right;
			}
			else if (key < kot(cur->_data))
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur);
			}
		}

		return end();
	}

	~RBTree()
	{
		destroy(_root);
		_root = nullptr;
	}

	void destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		destroy(root->_left);
		destroy(root->_right);
		delete root;
	}

	//左单旋
	void RotateL(Node* root)
	{
		Node* Pparent = root->_parent;
	 
		Node* rootR = root->_right;
		Node* rootRL = rootR->_left;
	 
		root->_right = rootR->_left;
		if (rootRL)
			rootRL->_parent = root;
	 
		rootR->_left = root;
		root->_parent = rootR;
	 
		//root->_bf = rootR->_bf = 0;
		//if(rootRL)
		//	rootRL->_bf = 0;
	 
		if (root == _root)
		{
			_root = rootR;
			_root->_parent = nullptr;
		}
		else
		{
			if (Pparent->_left == root)
			{
				Pparent->_left = rootR;
				rootR->_parent = Pparent;
			}
			else if (Pparent->_right == root)
			{
				Pparent->_right = rootR;
				rootR->_parent = Pparent;
			}
			else
			{
				assert(false);
			}
		}
	}
	//右单旋
	void RotateR(Node* root)
	{
		Node* Pparent = root->_parent;
	 
		Node* rootL = root->_left;
		Node* rootLR = rootL->_right;
	 
		root->_left = rootL->_right;
		if (rootLR)
			rootLR->_parent = root;
	 
		rootL->_right = root;
		root->_parent = rootL;
	 
		//root->_bf = rootL->_bf = 0;
		//if(rootLR)
		//	rootLR->_bf = 0;
	 
		if (root == _root)
		{
			_root = rootL;
			_root->_parent = nullptr;
		}
		else
		{
			if (Pparent->_left == root)
			{
				Pparent->_left = rootL;
				rootL->_parent = Pparent;
			}
			else if (Pparent->_right == root)
			{
				Pparent->_right = rootL;
				rootL->_parent = Pparent;
			}
			else
			{
				assert(false);
			}
		}
	}
	
	//////左右单旋
	////void RotateLR(Node* root)
	////{
	////	Node* rootL = root->_left;
	////	Node* rootLR = rootL->_right;
	////	int bf = rootLR->_bf;
	//// 
	////	RotateL(rootL);
	////	RotateR(root);
	//// 
	////	if (bf == -1)
	////	{
	////		root->_bf = 1;
	////		rootL->_bf = 0;
	////		if (rootLR)
	////			rootLR->_bf = 0;
	////	}
	////	else if (bf == 1)
	////	{
	////		rootL->_bf = -1;
	////		root->_bf = 0;
	////		if (rootLR)
	////			rootLR->_bf = 0;
	////	}
	////	else if (bf == 0)
	////	{
	////		rootL->_bf = root->_bf = rootLR->_bf = 0;
	////	}
	////	else
	////	{
	////		assert(false);
	////	}
	////}
	//////右左单旋
	////void RotateRL(Node* root)
	////{
	////	Node* rootR = root->_right;
	////	Node* rootRL = rootR->_left;
	//// 
	////	int bf = rootRL->_bf;
	//// 
	////	RotateR(rootR);
	////	RotateL(root);
	//// 
	////	if (bf == -1)
	////	{
	////		root->_bf = -1;
	////		rootR->_bf = 0;
	////		rootRL->_bf = 0;
	////	}
	////	else if (bf == 1)
	////	{
	////		rootR->_bf = 1;
	////		root->_bf = 0;
	////		rootRL->_bf = 0;
	////	}
	////	else if (bf == 0)
	////	{
	////		rootR->_bf = root->_bf = rootRL->_bf = 0;
	////	}
	////	else
	////	{
	////		assert(false);
	////	}
	////}

	//Insert函数
	pair<Iterator, bool> Insert(T data)
	{
		KeyOfT getK;

		//第一次插入
		if (_root == nullptr)
		{
			_root = new Node(data);
			//根节点置黑
			_root->_col = BLACK;
			//return make_pair(_root, true);
			return make_pair(Iterator(_root), true);
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (getK(data) < getK(cur->_data))
			{
				//往右走
				parent = cur;
				cur = cur->_left;
			}
			else if (getK(data) > getK(cur->_data))
			{
				//往左走
				parent = cur;
				cur = cur->_right;
			}
			else //相等
			{
				return make_pair(Iterator(cur), false);
			}
		}
		//找到位置
		cur = new Node(data);
		if (getK(data) < getK(parent->_data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//开始检查红黑树性质是否遭到破坏

		Node* newNode = cur; //提前记录要返回的iterator
		//如果parent为黑，插入完成
		if (parent->_col == BLACK)
		{
			return make_pair(cur, true);
		}
		//如果parent为红，开始调整
		else
		{
			while (cur->_parent && cur->_parent->_col == RED) //如果parent为红，开始调整
			{
				//根据cur重置parent、grandparent、uncle
				parent = cur->_parent;
				Node* grandparent = parent->_parent;
				Node* uncle = nullptr;
				if (parent == grandparent->_left)
				{
					uncle = grandparent->_right;
				}
				else
				{
					uncle = grandparent->_left;
				}

				//情况一
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;	

					//grandparent作cur，继续向上调整
					cur = grandparent;
				}
				//情况二、三
				else //uncle不存在/uncle为黑
				{
					//情况二 单旋					 
					//       g
					//    p
					// c
					if (parent == grandparent->_left && cur == parent->_left)
					{
						RotateR(grandparent);
						//变色
						parent->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					// g
					//    p
					//       c
					else if (parent == grandparent->_right && cur == parent->_right)
					{
						RotateL(grandparent);
						//变色
						parent->_col = BLACK;
						grandparent->_col = RED;
						break;
					}

					//情况三 双旋					 
					//    g
					// p
					//    c
					else if (parent == grandparent->_left && cur == parent->_right)
					{
						RotateL(parent);
						RotateR(grandparent);
						//变色
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					// g
					//    p
					// c
					else if (parent == grandparent->_right && cur == parent->_left)
					{
						RotateR(parent);
						RotateL(grandparent);
						//变色
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					else
					{
						assert(false);
					}
				}
			}
		}
		
		//根节点置黑
		_root->_col = BLACK;
		return make_pair(Iterator(newNode), true);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_data << " ";
		_InOrder(root->_right);
	}

	void PrevOrder()
	{
		_PrevOrder(_root);
	}

	void _PrevOrder(Node* root)
	{
		if (root == NULL)
			return;

        cout << root->_data << " ";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}

	bool IsBalance()
	{
		//检测第二条性质，根节点是否为黑
		//if (_root->_col == RED)------->先检测根节点是否为空再访问其成员
		if (_root && _root->_col == RED)
		{
			return false;
		}

		//计算最左路径黑色节点的数目作基准值
		Node* root = _root;
		int banchmark = 0; //基准值		
		while (root)
		{
			if (root->_col == BLACK)
				banchmark++;

			root = root->_left;
		}

		int blackNum = 0;
		return _IsBalance(_root, blackNum, banchmark);
	}

	bool _IsBalance(Node* root, int blackNum, int banchmark)
	{
		//检测
		
		//检查性质三，各路径黑节点数目是否相同
		if (root == nullptr)
		{
			return blackNum == banchmark;
		}

		if (root->_col == BLACK)
			blackNum++;

		//检查性质三，是否有连续红节点
		if (root->_col == RED && root->_parent->_col == RED)
			return false;

		return _IsBalance(root->_left, blackNum, banchmark)
			&& _IsBalance(root->_right, blackNum, banchmark);
	}

	Iterator begin()
	{
		Node* l = _root;
		while (l->_left)
		{
			l = l->_left;
		}
		return Iterator(l);
	}
	
	Iterator end()
	{
		//Node* r = _root;
		//while (r->_right)
		//{
		//	r = r->_right;
		//}
		//return Iterator(r);

		return Iterator(nullptr); // end是最后一个节点的下一个，故不能返回最右节点
	}


private:
	Node* _root;
};
